Parsing has been pursued with tremendous efforts in the Natural Language Processing (NLP) community. Since the introduction of lexicalized probabilistic context-free grammar (PCFGs) parsers, improvements have been achieved over the years, but generative PCFGs parsers of the last decade still remain standard benchmarks. Given the success of discriminative learning algorithms for classical NLP tasks (Part-Of-Speech (POS) tagging, Name Entity Recognition, Chunking . . . ), the generative nature of such parsers has been questioned. First, discriminative parsing algorithms have not reached the performance of standard PCFG-based generative parsers. The parser reported in DISCRIMINATIVE TRAINING OF A NEURAL NETWORK STATISTICAL PARSER, by J. Henderson outperforms the parser reported in HEAD-DRIVEN STATISTICAL MODELS FOR NATURAL LANGUAGE PARSING, by M. Collins, only by using a generative model and performing re-ranking. The pure discriminative parsers reported in MAX-MARGIN PARSING, by B. Taskar et al. and ADVANCES IN DISCRIMINATIVE PARSING by J. Turian et al. finally reached Collins' parser performance, with various simple template features. However, these parsers are slow to train and are limited to sentences with less than 15 words. Most recent discriminative parsers are based on Conditional Random Fields (CRFs) with PCFG-like features.
Accordingly, there is a need for a fast discriminative parser which does not rely on information extracted from PCFG's or on most classical parsing features.